Summary and Contributions: The Baxter Permutation Process provides a generalization of the Mondrian process so that an arbitrary tiling with hyperrectables is supported. In particular, the Mondrian process (MP) is a Bayesian nonparametric version of a decision tree. Since MP is defined by a tree, each cut must extend to the edges of the hyperrectangle being cut. This means that the first cut must extend from -infinity to infinity, and the second cut (should it be perpendicular) must extend from infinity to the level of the first cut (or, if it's parallel, again from -infinity to infinity). This extensive cut nature is not incredibly terrible, but could lead to a lack of local modelling.

In this paper, a Bayesian nonparametric (BNP) model for Baxter permutations (BPs), termed BP process (BPP) is proposed and applied to relational data analysis. The BPs are a well-studied class of permutations, and it has been demonstrated that there is one-to-one correspondence between BPs and several interesting objects including floorplan partitioning (FP), which constitutes a subset of rectangular partitioning (RP). Accordingly, the BPP can be used as an FP model. We combine the BPP with a multi-dimensional extension of the stick-breaking process called the {\it block-breaking process} to fill the gap between FP and RP, and obtain a stochastic process on arbitrary RPs. Compared with conventional BNP models for arbitrary RPs, the proposed model is simpler and has a high affinity with Bayesian inference.